//给定一个 24 小时制（小时:分钟 "HH:MM"）的时间列表，找出列表中任意两个时间的最小时间差并以分钟数表示。 
//
// 
//
// 示例 1： 
//
// 
//输入：timePoints = ["23:59","00:00"]
//输出：1
// 
//
// 示例 2： 
//
// 
//输入：timePoints = ["00:00","23:59","00:00"]
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 2 <= timePoints.length <= 2 * 10⁴ 
// timePoints[i] 格式为 "HH:MM" 
// 
// Related Topics 数组 数学 字符串 排序 👍 182 👎 0

package com.cute.leetcode.editor.cn;

import java.util.Arrays;
import java.util.List;

public class MinimumTimeDifference {
    public static void main(String[] args) {
        Solution solution = new MinimumTimeDifference().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 存储时间后按照时-分由小到大排序，遍历时间进行统计，最后计算跨过0点的情况
         */
        public int findMinDifference1(List<String> timePoints) {
            int len = timePoints.size();
            int[][] allTime = new int[len][2];//0处记录小时，1处记录分钟
            for (int i = 0; i < len; i++) {
                allTime[i][0] = Integer.parseInt(timePoints.get(i).substring(0,2));
                allTime[i][1] = Integer.parseInt(timePoints.get(i).substring(3,5));
            }
            Arrays.sort(allTime, (a,b) -> {
                if (a[0] == b[0]) return a[1]-b[1];
                else return a[0] - b[0];
            });
            int res = Integer.MAX_VALUE;
            for (int i = 1; i < len ; i++)
                res = Math.min(res, (allTime[i][0]-allTime[i-1][0]) * 60 + (allTime[i][1] - allTime[i-1][1]));

            int last;//计算跨过0点的情况
            if (allTime[len-1][1] == 0) last = (24-allTime[len-1][0] + allTime[0][0]) * 60 + allTime[0][1];
            else last = (23-allTime[len-1][0] + allTime[0][0]) * 60 + (60 - allTime[len-1][1] + allTime[0][1]);
            return Math.min(res, last);
        }

        /**
         * 直接记录与0点的时间差，然后对时间差进行排序
         * 时间复杂度nlogn 空间复杂度n
         * 这个提交之后是最快的
         */
        public int findMinDifference2(List<String> timePoints) {
            int len = timePoints.size();
            if (len > 1440) return 0;
            int[] cache = new int[len];
            for (int i = 0; i < len; i++) {
                String s = timePoints.get(i);
                cache[i] = Integer.parseInt(s.substring(0,2)) * 60 + Integer.parseInt(s.substring(3));
            }
            Arrays.sort(cache);
            int res = Integer.MAX_VALUE;
            for (int i = 1; i < len; i++)
                res = Math.min(res, cache[i]-cache[i-1]);
            return Math.min(res, cache[0] + 1440 - cache[len-1]);
        }

        /**
         * 利用桶排序的思想，对每个时间点进行统计
         * 一天之内只有1440个时间点，两天的话也只有1440 * 2
         * 时空间复杂度都是C
         */
        public int findMinDifference(List<String> timePoints) {
            int len = timePoints.size();
            if (len > 1440) return 0;
            int[] counts = new int[1440 * 2 + 1];
            for (String s : timePoints){
                int time = Integer.parseInt(s.substring(0,2)) * 60 + Integer.parseInt(s.substring(3));
                counts[time]++;
                counts[time + 1440]++;
            }
            int ans = Integer.MAX_VALUE, index = -1;
            for (int i = 0; i <= 1440*2 ; i++) {
                if (counts[i] == 0) continue;
                if (counts[i] > 1) return 0;
                if (index != -1) ans = Math.min(ans, i-index);
                index = i;//index其实就是在记录时间
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}